<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    472. Concatenated Words
   </h1>
   Given a list of words (
   <b>
    without duplicates
   </b>
   ), please write a program that returns all concatenated words in the given list of words.
   <p>
    A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
   </p>
   <p>
    <b>
     Example:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

<b>Output:</b> ["catsdogcats","dogcatsdog","ratcatdogcat"]

<b>Explanation:</b> "catsdogcats" can be concatenated by "cats", "dog" and "cats"; <br> "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; <br>"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
</pre>
   <p>
    <b>
     Note:
    </b>
    <br>
   </p>
   <ol>
    <li>
     The number of elements of the given array will not exceed
     <code>
      10,000
     </code>
    </li>
    <li>
     The length sum of elements in the given array will not exceed
     <code>
      600,000
     </code>
     .
    </li>
    <li>
     All the input string will only include lower case letters.
    </li>
    <li>
     The returned elements order does not matter.
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    472. 连接词
   </h1>
   <p>
    给定一个
    <strong>
     不含重复
    </strong>
    单词的列表，编写一个程序，返回给定单词列表中所有的连接词。
   </p>
   <p>
    连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。
   </p>
   <p>
    <strong>
     示例:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

<strong>输出:</strong> ["catsdogcats","dogcatsdog","ratcatdogcat"]

<strong>解释:</strong> "catsdogcats"由"cats", "dog" 和 "cats"组成; 
     "dogcatsdog"由"dog", "cats"和"dog"组成; 
     "ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。
</pre>
   <p>
    <strong>
     说明:
    </strong>
   </p>
   <ol>
    <li>
     给定数组的元素总数不超过
     <code>
      10000
     </code>
     。
    </li>
    <li>
     给定数组中元素的长度总和不超过
     <code>
      600000
     </code>
     。
    </li>
    <li>
     所有输入字符串只包含小写字母。
    </li>
    <li>
     不需要考虑答案输出的顺序。
    </li>
   </ol>
  </div>
 </body>
</html>